import collections


class Solution(object):
    def maxScoreWords(self, words, letters, score):
        c = collections.Counter(letters)
        d = [0] * 26
        n = len(words)
        for i in range(26):
            d[i] = c[chr(ord('a') + i)]
        word_list = [[0 for _ in range(26)] for _ in range(n)]
        for index, word in enumerate(words):
            c = collections.Counter(list(word))
            for i in range(26):
                word_list[index][i] = c[chr(ord('a') + i)]
        max_score = 0
        for val in range(1 << n):
            t = [0] * 26
            for i in range(n):
                if (val >> i) & 1:
                    for j in range(26):
                        t[j] += word_list[i][j]
            now_score = 0
            for j in range(26):
                if t[j] <= d[j]:
                    now_score += score[j] * t[j]
                else:
                    now_score = 0
                    break
            if now_score > max_score:
                max_score = now_score
        return max_score



data = Solution()
words = ["dog","cat","dad","good"]
letters = ["a","a","c","d","d","d","g","o","o"]
score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
print(data.maxScoreWords(words, letters, score))